package studyNote.test;

public class BinarySearch {

    /**
     * 二分查找
     *
     * @param arr 要查找的数组
     * @param des 要查找的数
     * @return 要查找的数所在的位置
     */
    public static int binarySearch(int[] arr, int des) {
        // 设左边界初始值为0，右边界为arr.length-1，开启循环，循环跳出条件为left>right
        // 设middle，值为left和right下标的平均值，如果arr[middle]等于目标值，直接返回
        // 如果大于目标值，则right-1；如果小于目标值，则left+1；循环结束还未找到，表示不存在，返回-1
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int middle = (left + right) / 2;
            if (arr[middle] == des) {
                return middle;
            } else if (arr[middle] > des) {
                right--;
            } else {
                left++;
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{1, 7, 21, 30, 55, 60, 100, 120, 200, 300};

        System.out.println(binarySearch(arr, 222));
    }


}
